package String_process;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
/**
 * @author dx
 * @version 1.0
 * @date 2022/5/11 17:06
 * @description:  输入一个字符串，打印出该字符串中字符的所有排列
 * 回溯：https://zhuanlan.zhihu.com/p/93530380
 */
public class Permutation {
    public static void main(String[] args) {
        Scanner sr = new Scanner(System.in);
        String s = sr.nextLine();
        List<List<Character>> res = new LinkedList<>();
        System.out.println(new Permutation_solution().permutation(s));
    }
}

class Permutation_solution{
    List<List<Character>> res = new LinkedList<>();
    //输入字符串
    public List<List<Character>> permutation(String s){
        char x[] = s.toCharArray();

        //记录路径
        LinkedList<Character> track = new LinkedList<>();
        backtrace(x,track);
        return res;

    }
    public void backtrace(char []s,LinkedList<Character> track){
        //触发结束条件:当路径长度等于全排列的长度，则添加到返回值里面
        if(track.size() == s.length){
            res.add(new LinkedList<>(track));
            return;
        }
        for(int i = 0; i < s.length; i++){
            //排除不合法的选择
            if(track.contains(s[i])){
                continue;
            }
            //做选择:加到track中
            track.add(s[i]);
            //进入到下一层决策树
            backtrace(s,track);
            //取消选择：当下一层一到了最底层，则开始取消其（最底层）“当前节点”的选择
            track.removeLast();
        }
    }
    //以两个节点为例：String s = ab
    /*
     第一层                                            ----》 第二层
     1、for i =1                                         1、for 1 continue,for 2:
     2、trace add(a)                                     2、trace add(ab)

                                                        3、backtrace()            ---------------> track.size() == s.length
                                                                                             /
                                                                                           /
     3、backtrace()  ------> 进入第二层                  4、  ----------------- trace.removeLast
                                                               |
                                                               |
                                                               |
                                                            trace:a （b删除）,并且for循环结束
                                                            /
                                                          /
                                                         /
                                     4、trace.removeLast()
                                            |
                                            |
                                            |
                                            trace :空,进入下一个循环
       5、for i =2
       6、 trace add(b)





                                           ====》第二层
                                           1、for  i= 1
                                           2、trace add(ba)

                                           3、backtrace()                            ------>trace.size() == s.length
                                                                                         /
                                                                                        /
                                                                                       /
       7、backtrace()  ------>进入第二层      4、-------------------------------trace.removeLast
                                                  |
                                                  |
                                                  |
                                                  trace: b(a删除)，并且for进入i = 2 continue,结束循环
                                                   /
                                                 /
                                               /
                                         8、trace.removeLast()
                                               |
                                               |
                                               |
                                               trace:空，结束程序

     */




}
